The present invention relates to a method of image processing and an image processing apparatus. In particular, the present invention relates to the rendering of images composed from a number of discrete polygonal surfaces, known as image primitives.
It is a common technique in real time consumer graphics to model objects as meshes of polygons,especially triangles for ease of handling. This is particularly the case for three-dimensional object modelling wherein, to obtain a two-dimensional image from three-dimensional image data, the polygons making up the object surface in three-dimensional space are projected into two-dimensional space and, following any necessary calculation or reference to look-up tables, appropriate pixel values (including colour, texture etc.) are mapped onto pixel positions within the projected two-dimensional polygon. The calculation following the translation of the polygons from three- to two-dimensional space is suitably handled by a processor pipeline in order to produce the set of display pixel values.
An example of such a processor pipeline for use in a 3D graphics display system, and comprising a series coupled chain of polygon processors, is described in U.S. Pat. No. 4,855,703 (Deering/Schlumberger). Following translation of polygons from three to two dimensions, the polygons are sorted into scan order by reference to the first display pixel line on which they appear. Prior to processing of a scan line, each newly-introduced polygon is loaded into a respective one of the processors in the chain where they are also stored, such that their contribution to successive scan lines may also be derived. When a scan line is reached which is not covered by a particular polygon (i.e. the first clear line below the bottom vertex of, say, a triangular polygon), that polygon is unloaded from the processor in the chain to make way for new polygon data. After processing of a scan line, the pixel data for that line may be sent directly to a display (such as a cathode ray tube [CRT] device) or may be stored in a frame buffer for later accessing.
Before the scan line processing can begin, there is the preliminary process of preparing the two-dimensional polygons which requires, amongst other actions, the calculation of edge slopes, which preliminary process can often consume sufficient computational resources to limit the overall performance of the system. A technique which seeks to simplify this stage somewhat is described in U.S. Pat. No. 4,930,091 (Schroeder & Deering/Schlumberger) which technique is applied to the system of the above-referenced U.S. Pat. No. 4,855,703. In the technique, a triangle classification is introduced whereby a plurality of parameters of a triangle are calculated from the supplied coordinates of the vertices. These parameters are then used to address a look-up table containing a triangle classification with all possible forms of triangle being covered by the varying combinations of parameters: the triangle classification, once read from the look-up table, determines how that triangle is to be processed in the pipeline. In the case of degenerate triangles, where all three vertices lie on a line (such that the triangle itself is just a line) or they are so close together that the triangle does not enclose a pixel (and hence would not show up in the displayed image) no further processing is undertaken.